package 剑指offer;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-12-09 9:51
 */
public class day29_19_49_60 {

    /**==============================================================================================================================================
     * 剑指 Offer 19. 正则表达式匹配
     * 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。
     * dp(s,i,p,j) = true，则表示s[i..]可以匹配p[j..]；若dp(s,i,p,j) = false，则表示s[i..]无法匹配p[j..]。
     * 1.1 *通配符匹配 0 次或多次:i加 1，j不变，含义就是p[j]匹配了s[i]，但p[j]还可以继续匹配
     * 1.2 常规匹配 1 次:无*的常规匹配，那么如果s[i] == p[j]，就是i和j分别加一
     * 2.1 通配符匹配 0 次:将j加 2，i不变
     * 2.2 如果没有*通配符，也无法匹配，那只能说明匹配失败了：
     *  */
    Map<String,Boolean> memo=new HashMap<>();
    boolean dp(String s,int i,String p,int j){
        int m=s.length(),n=p.length();
        //base case
        if (j==n){
            //p串到末尾
            return i==m;
        }
        if (i==m){
            //s到最后，判断p是否可以匹配空串,只能是a*b*这种模式
            if ((n-j)%2==1)return false;
            for (; j+1 < n; j+=2) {
                if (p.charAt(j+1)!='*'){
                    return false;
                }
            }
            return true;
        }

        //记录状态用于存放到memo
        String key=i+","+j;
        if (memo.containsKey(key)){
            return memo.get(key);
        }

        boolean res=false;
        if (s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
            if (j<n-1&&p.charAt(j+1)=='*'){
                //1.1 *通配符匹配 0 次或多次:i加 1，j不变，含义就是p[j]匹配了s[i]，但p[j]还可以继续匹配
                res=dp(s,i,p,j+2)||dp(s,i+1,p,j);
            }else {
                //1.2 常规匹配 1 次:无*的常规匹配，那么如果s[i] == p[j]，就是i和j分别加一
                res=dp(s,i+1,p,j+1);
            }
        }else {
            if (j<n-1&&p.charAt(j+1)=='*'){
                //2.1 通配符匹配 0 次:将j加 2，i不变,当前两个字符不匹配，但是p后面有*
                res=dp(s,i,p,j+2);
            }else {
                //2.2 如果没有*通配符，也无法匹配，那只能说明匹配失败了：
                res=false;
            }
        }
        memo.put(key,res);
        return res;
    }
    public boolean isMatch(String s, String p) {
        return dp(s,0,p,0);
    }

    /**==============================================================================================================================================
     * 剑指 Offer 49. 丑数
     * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
     * 从1开始，将每个丑数加入队列中，同时将该丑数的2，3，5，倍都加入优先队列
     *  */
    public int nthUglyNumber(int n) {
        if (n==1) return 1;
        int[] primes=new int[]{2,3,5};
        Set<Long> set=new HashSet<>();
        PriorityQueue<Long> pq=new PriorityQueue<>();
        set.add(1L);
        pq.offer(1L);
        int res=0;
        for (int i = 0; i < n; i++) {
            Long cur = pq.poll();
            res= Math.toIntExact(cur);
            for (int p:primes) {
                Long temp=p*cur;
                if (set.add(temp)){
                    pq.offer(temp);
                }
            }
        }
        return res;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 60. n个骰子的点数
     * 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
     * n 个骰子「点数和」的范围为 [n, 6n] ，数量为 6n - n + 1 = 5n + 1种。
     * dp[i][j]代表前 i 个骰子的点数和 j 的概率，并执行状态转移。
     *  */
    public double[] dicesProbability(int n) {
        double[] dp=new double[6];
        Arrays.fill(dp,1.0/6.0);
        for (int i = 2; i <=n ; i++) {
            double[] temp=new double[5*i+1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    temp[j+k]+=dp[j]/6.0;
                }
            }
            dp=temp;
        }
        return dp;
    }

}
